package leetcode.code2225;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public List<List<Integer>> findWinners(int[][] matches) {
		int len = matches.length;
		int[] winners = new int[len];
		int[] losers = new int[len];
		for (int i = 0; i < matches.length; i++) {
			int[] cur = matches[i];
			int win = cur[0], lost = cur[1];
			winners[i] = win;
			losers[i] = lost;
		}
		Arrays.sort(winners);
		Arrays.sort(losers);
//		H.printObject(winners);
//		H.printObject(losers);
//		[1,2,3,4,4,4,5,5,10,10,]
//		[3,3,4,5,6,6,7,8,9,9,]
		List<Integer> winAns = new ArrayList<>();
		List<Integer> loseAns = new ArrayList<>();
		int p1 = 0, p2 = 0;
		int lastWinner = 0, lastp2 = 0;
		while (p1 < len && p2 < len) {
			int winner = winners[p1];
			if (winner == lastWinner) {
				p1++;
				continue;
			}
			while (p2 < len && losers[p2] < winner) {
				if (losers[p2] != losers[lastp2]) {
					if (p2 - lastp2 == 1) {
						loseAns.add(losers[lastp2]);
					}
					lastp2 = p2;
				}
				p2++;
			}
			if (p2 < len) {
				if (losers[p2] > winner) {
					winAns.add(winner);
					lastWinner = winner;
				}
				p1++;
			}
		}
		while (p1 < len) {
			int winner = winners[p1];
			if (winner == lastWinner) {
				p1++;
				continue;
			}
			winAns.add(winner);
			lastWinner = winner;
		}
		while (p2 < len) {
			if (losers[p2] != losers[lastp2]) {
				if (p2 - lastp2 == 1) {
					loseAns.add(losers[lastp2]);
				}
				lastp2 = p2;
			}
			p2++;
		}
		if (lastp2 == len - 1) {
			loseAns.add(losers[lastp2]);
		}
		List<List<Integer>> ans = new ArrayList<>();
		ans.add(winAns);
		ans.add(loseAns);
		return ans;
	}

	@Override
	public void debug4() {
		this.findWinners(H.str2array1("[[2,3],[1,3],[5,4],[6,4]]"));
		this.findWinners(H.str2array1("[[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
